package MyBinaryTree;

import java.util.Stack;

public class BinaryTree {

    private int data;
    private BinaryTree left;
    private BinaryTree right;

    public BinaryTree(int data, BinaryTree left, BinaryTree right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public BinaryTree(int data) {
        this.data = data;
    }

    //前序遍历
    public void preRecursion(BinaryTree node){
        if(node == null){
            return;
        }
        System.out.print(node.data + " ");
        preRecursion(node.left);
        preRecursion(node.right);
    }

    //中序遍历
    public void midRecursion(BinaryTree node){

        if(node == null){
            return;
        }

        midRecursion(node.left);
        System.out.print(node.data + " ");
        midRecursion(node.right);

    }

    //后序遍历
    public void postRecursion(BinaryTree node){
        if (node == null){
            return;
        }

        postRecursion(node.left);
        postRecursion(node.right);
        System.out.print(node.data + " ");
    }


    //迭代前序遍历
    public void pre(){
        BinaryTree node = this;
        Stack<BinaryTree> stack = new Stack<>();

        while (node != null || !stack.isEmpty()){
            if (node != null){
                System.out.println(node.data);
                stack.push(node);
                node = node.left;
            }else {
                BinaryTree pop = stack.pop();
                node = pop.right;
            }
        }
    }

    //迭代中序遍历
    public void mid(){
        BinaryTree node = this;
        Stack<BinaryTree> stack = new Stack<>();
        while (node != null || !stack.isEmpty()){
            if (node != null){
                stack.push(node);
                node = node.left;
            }else {
                BinaryTree pop = stack.pop();
                System.out.println(pop.data);
                node = pop.right;
            }
        }
    }

    //迭代遍历后序
    public void post(){
        BinaryTree node = this;
        Stack<BinaryTree> stack = new Stack<>();
        BinaryTree pop = null;
        while (node != null || !stack.isEmpty()){
            if (node != null){
                stack.push(node);
                node = node.left;
            }else {
                BinaryTree peek = stack.peek();
                if (peek.right == null || peek.right == pop){
                    pop = stack.pop();
                    System.out.print(pop.data + " ");
                }else {
                    node = peek.right;
                }
            }

        }
    }

    //求二叉树最大深度
    public int maxDeep(BinaryTree node){
        if (node == null){
            return 0;
        }
        int l = maxDeep(node.left);
        int r = maxDeep(node.right);
        return (Math.max(l,r) + 1);
    }

    //求二叉树的节点个数，利用前序遍历即可
    private int count = 0;
    public int getCount(BinaryTree node){
        countNode(node);
        return count;
    }
    public void countNode(BinaryTree node){
        if (node == null){
            return;
        }
        count++;
        countNode(node.left);
        countNode(node.right);
    }


}
